P5769 [JSOI2016]飞机调度

网络流24题

为了使飞机数量尽量少，一架飞机尽量多飞几趟航班。

将航班看成一个点，其实就是求最小路径覆盖。

如果 $i,j$ 航班可以由一架飞机先后飞行，那么将 $i,j$ 连一条边。

现在考虑如何判断可先后进行的航班。

可以用 $\text{Floyd}$ 处理由机场 $i$ 到 $j$ ，且可以立即起飞的最短时间 $dis(i,j)$。

那么只需要满足：

$d[i]+ T(x_i,y_i)+p_{y_i}+dis(y_i,x_j) \le d[j]$

Dinic需要加当前弧优化。 应该都知道吧。

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define Inf 0x3f3f3f3f

template<typename _T>
void Read( _T &x ) {
	x = 0; int f = 1;
	char s = getchar( );
	for( ; s < '0' || s > '9' ; s = getchar( ) ) f = s == '-' ? -f : f;
	for( ; s >= '0' && s <= '9' ; s = getchar( ) ) x = x * 10 + s - '0';
	x *= f;
}
template<typename _T>
void Write( _T x ) {
	if( x < 0 ) putchar( '-' ) , x = -x;
	if( x >= 10 ) Write( x / 10 );
	putchar( x % 10 + '0' );
}

const int MAXN = 500 , MAXM = 260000;
struct node {
	int v , flow , nxt;
}Graph[ MAXM + 5 ];
int tot = 1 , Head[ 2 * MAXN + 5 ];
void Add_Edge( int u , int v , int f ) {
	Graph[ ++ tot ] = { v , f , Head[ u ] };
	Head[ u ] = tot;
}

int n , m , S , T , p[ MAXN + 5 ] , t[ MAXN + 5 ][ MAXN + 5 ] , dis[ MAXN + 5 ][ MAXN + 5 ];
int x[ MAXN + 5 ] , y[ MAXN + 5 ] , tim[ MAXN + 5 ];
int lev[ 2 * MAXN + 5 ] , cur[ 2 * MAXN + 5 ];
bool Layering( int s , int t ) {
    memset( lev , -1 , sizeof( lev ) );
	memcpy( cur , Head , sizeof( Head ) );
    queue< int > Que;
    Que.push( s ) , lev[ s ] = 0;
    while( !Que.empty( ) ) {
        int u = Que.front( ); Que.pop( );
        for( int i = Head[ u ] ; i ; i = Graph[ i ].nxt ) {
            int v = Graph[ i ].v , flw = Graph[ i ].flow;
            if( flw > 0 && lev[ v ] == -1 )
                lev[ v ] = lev[ u ] + 1 , Que.push( v );
        }
    }
    return lev[ t ] != -1;
}
int dfs( int u , int t , int f ) {
	if( u == t ) return f;
	for( int i = cur[ u ] ; i ; i = Graph[ i ].nxt ) {
		int v = Graph[ i ].v , flw = Graph[ i ].flow;
		cur[ u ] = i;
		if( flw > 0 && lev[ v ] == lev[ u ] + 1 ) {
			int mf = dfs( v , t , min( f , flw ) );
			if( mf ) {
				Graph[ i ].flow -= mf; Graph[ i ^ 1 ].flow += mf;
				return mf;
			}
		}
	}
	return 0;
}
int Dinic( int s , int t ) {
	int Maxf = 0;
	while( Layering( s , t ) ) for( int fl ; ( fl = dfs( s , t , Inf ) ) > 0 ; Maxf += fl );
	return Maxf;
}
void MakeGraph( ) {
	S = 2 * m + 1 , T = 2 * m + 2;
	for( int i = 1 ; i <= m ; i ++ )
		Add_Edge( S , i , 1 ) , Add_Edge( i , S , 0 );
	for( int i = 1 ; i <= m ; i ++ )
		Add_Edge( i + m , T , 1 ) , Add_Edge( T , i + m , 0 );
	for( int i = 1 ; i <= m ; i ++ )
		for( int j = 1 ; j <= m ; j ++ )
			if( tim[ i ] + t[ x[ i ] ][ y[ i ] ] + p[ y[ i ] ] + dis[ y[ i ] ][ x[ j ] ] <= tim[ j ] )
				Add_Edge( i , j + m , 1 ) , Add_Edge( j + m , i , 0 );
}

void Floyd( ) {
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = 1 ; j <= n ; j ++ )
			if( i ^ j ) dis[ i ][ j ] = t[ i ][ j ] + p[ j ];
	for( int k = 1 ; k <= n ; k ++ )
		for( int i = 1 ; i <= n ; i ++ )
			for( int j = 1 ; j <= n ; j ++ )
				if( dis[ i ][ j ] > dis[ i ][ k ] + dis[ k ][ j ] )
					dis[ i ][ j ] = dis[ i ][ k ] + dis[ k ][ j ];
}

int main( ) {
	Read( n ) , Read( m );
	for( int i = 1 ; i <= n ; i ++ )
		Read( p[ i ] );
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = 1 ; j <= n ; j ++ )
			Read( t[ i ][ j ] );
	for( int i = 1 ; i <= m ; i ++ )
		Read( x[ i ] ) , Read( y[ i ] ) , Read( tim[ i ] );
	
	Floyd( );
	MakeGraph( );
	Write( m - Dinic( S , T ) ) , putchar('\n');
	return 0; 
}